package 树.递归;

public class 打家劫舍III_337 {
    public int rob(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int val1 = root.val;//第一种情况，偷根节点root

        if (root.left != null) {//对左子树来说
            // 如果根节点被偷了，且根节点的左子树不为0，那么就可以偷根节点的孙子节点
            val1 = val1 + rob(root.left.left) + rob(root.left.right);
        }

        if (root.right != null) {//对右子树来说
            // 如果根节点被偷了，且根节点的右子树不为0，那么就可以偷根节点的孙子节点
            val1 = val1 + rob(root.right.left) + rob(root.right.right);
        }

        int val2 = rob(root.left) + rob(root.right);//第二种情况，不偷根节点，那么为了偷取的金额最高，就去偷它的子节点

        return Math.max(val1, val2);//看看两种情况那个偷的钱更多

    }
}
